/**
 * @file node_set_test.cpp
 *
 * @author Anthony Foiani <anthony.foiani@gmail.com>
 *
 * License: Boost License v1.0 -- http://www.boost.org/users/license.html
 *
 * Compile line:
 *   g++ -std=c++0x -O3 -o node_set_test node_set_test.cpp
 */

#include <cmath>
#include <iostream>

#include <boost/test/minimal.hpp>

#include <boost/smart_ptr/make_shared.hpp>

#include "../node_set.hpp"

#ifndef NDEBUG
#  include <iostream>
#  define DEBUG( x ) std::clog << "node_set_test: " << x << std::endl
#  define IF_DEBUGGING( x ) do { x; } while ( 0 )
#else
#  define DEBUG( x ) do {} while ( 0 )
#  define IF_DEBUGGING( x ) do {} while ( 0 )
#endif

namespace
{

void testBasics()
{
	class node_t
	{

	public:

		typedef std::string State;
		typedef double      PathCost;

		node_t() : _state( "_uninitialized" ), _path_cost( 0.0 ) {}
		node_t( const State & state, const PathCost & path_cost )
			: _state( state ), _path_cost( path_cost ) {}

		const State    & state()     const { return _state; }
		const PathCost & path_cost() const { return _path_cost; }

	private:

		State _state;
		PathCost _path_cost;

	};

	typedef boost::shared_ptr< node_t > node_ptr_t;

	typedef jsearch::node_set< node_ptr_t > my_node_set_t;

	my_node_set_t nodes;

	node_ptr_t np;

	BOOST_CHECK( nodes.empty() );

	DEBUG( "inserting (a, 5.0, '')" );
	np = boost::make_shared< node_t >( "a", 5.0 );
	BOOST_CHECK( nodes.insert_or_update( np ) );

	BOOST_CHECK( ! nodes.empty() );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	{
		DEBUG( "getting by id (existing)" );
		BOOST_CHECK( np = nodes.get_node_by_id( "a" ) );
		BOOST_CHECK( np->state()     == "a" );
		BOOST_CHECK( np->path_cost() == 5.0 );

		DEBUG( "getting by id (non-existant)" );
		BOOST_CHECK( ! ( np = nodes.get_node_by_id( "b" ) ) );

		DEBUG( "getting min node" );
		BOOST_CHECK( np = nodes.get_min_cost_node() );
		BOOST_CHECK( np->state()     == "a" );
		BOOST_CHECK( np->path_cost() == 5.0 );
	}

	DEBUG( "inserting (b, 3.0, '')" );
	np = boost::make_shared< node_t >( "b", 3.0 );
	BOOST_CHECK( nodes.insert_or_update( np ) );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	{
		DEBUG( "getting by id (existing)" );
		BOOST_CHECK( np = nodes.get_node_by_id( "b" ) );
		BOOST_CHECK( np->state()     == "b" );
		BOOST_CHECK( np->path_cost() == 3.0 );

		DEBUG( "getting min node" );
		BOOST_CHECK( np = nodes.get_min_cost_node() );
		BOOST_CHECK( np->state()     == "b" );
		BOOST_CHECK( np->path_cost() == 3.0 );
	}

	DEBUG( "updating (a, 2.0, '')" );
	np = boost::make_shared< node_t >( "a", 2.0 );
	BOOST_CHECK( nodes.insert_or_update( np ) );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	DEBUG( "updating (a, 6.0, '')" );
	np = boost::make_shared< node_t >( "a", 6.0 );
	BOOST_CHECK( ! nodes.insert_or_update( np ) );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	{
		DEBUG( "getting by id (existing)" );
		BOOST_CHECK( np = nodes.get_node_by_id( "a" ) );
		BOOST_CHECK( np->state()     == "a" );
		BOOST_CHECK( np->path_cost() == 2.0 );

		DEBUG( "getting min node" );
		BOOST_CHECK( np = nodes.get_min_cost_node() );
		BOOST_CHECK( np->state()     == "a" );
		BOOST_CHECK( np->path_cost() == 2.0 );
	}

	DEBUG( "deleting 'a'" );
	nodes.get_and_pop_node_by_id( "a" );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	{
		DEBUG( "getting by id (non-existant)" );
		BOOST_CHECK( ! ( np = nodes.get_node_by_id( "a" ) ) );

		DEBUG( "getting by id (existing)" );
		BOOST_CHECK( np = nodes.get_node_by_id( "b" ) );
		BOOST_CHECK( np->state()     == "b" );
		BOOST_CHECK( np->path_cost() == 3.0 );

		DEBUG( "getting min node" );
		BOOST_CHECK( np = nodes.get_min_cost_node() );
		BOOST_CHECK( np->state()     == "b" );
		BOOST_CHECK( np->path_cost() == 3.0 );
	}

	DEBUG( "deleting min cost" );
	BOOST_CHECK( nodes.get_and_pop_min_cost_node() );

	IF_DEBUGGING( nodes.dump( std::clog ) );

	{
		DEBUG( "getting by id (non-existant)" );
		BOOST_CHECK( ! ( np = nodes.get_node_by_id( "a" ) ) );

		DEBUG( "getting by id (non-existant)" );
		BOOST_CHECK( ! ( np = nodes.get_node_by_id( "b" ) ) );
	}

	BOOST_CHECK( nodes.empty() );

	{
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "a", 10.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "b",  9.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "c",  8.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "d",  7.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "e",  6.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "f",  5.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "g",  4.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "h",  3.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "i",  2.0 ) ) );
		BOOST_CHECK( nodes.insert_or_update( boost::make_shared< node_t >( "j",  1.0 ) ) );

		BOOST_CHECK( ! nodes.empty() );
		BOOST_CHECK( nodes.size() == 10 );

		IF_DEBUGGING( nodes.dump( std::clog ) );

		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "j" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "i" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "h" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "g" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "f" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "e" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "d" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "c" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "b" );
		BOOST_CHECK( np = nodes.get_and_pop_min_cost_node() );
		BOOST_CHECK( np->state() == "a" );

		BOOST_CHECK( nodes.empty() );
		BOOST_CHECK( nodes.size() == 0 );
	}
}

// =====================================================================

#if 0

double str_to_double( const std::string & s )
{
	std::istringstream iss( s );
	double rv;
	iss >> rv;
	return rv;
}

double str_to_int( const std::string & s )
{
	std::istringstream iss( s );
	int rv;
	iss >> rv;
	return rv;
}

struct City
{
	std::string name;
	double lat;
	double lon;
};

typedef std::vector< City > CityVec;

const CityVec cities{
	{ "Alamagordo",     32.900412, -105.960479 },
	{ "Albuquerque",    35.110703, -106.609991 },
	{ "Artesia",        32.842778, -104.412222 },
	{ "Carlsbad",       32.411944, -104.236389 },
	{ "Carrizozo",      33.643889, -105.877500 },
	{ "Clines Corners", 34.960500, -105.561000 },
	{ "Deming",         32.268698, -107.758640 },
	{ "Gallup",         35.528078, -108.742584 },
	{ "Grants",         35.155278, -107.842222 },
	{ "Las Cruces",     32.319722, -106.765278 },
	{ "Las Vegas",      35.596944, -105.222500 },
	{ "Los Alamos",     35.891111, -106.297778 },
	{ "Lordsburg",      32.350361, -108.708665 },
	{ "Raton",          36.896944, -104.440000 },
	{ "Roswell",        33.387222, -104.528056 },
	{ "Santa Fe",       35.667222, -105.964444 },
	{ "Socorro",        34.058400, -106.891416 }
};

struct Connection
{
	std::string city1;
	std::string city2;
	std::string via;
	double dist;
};

typedef std::vector< Connection > ConnectionVec;

const ConnectionVec connections{
	{ "Alamagordo",     "Artesia",        "US-82",         110 },
	{ "Alamagordo",     "Carrizozo",      "US-54",          57 },
	{ "Alamagordo",     "Las Cruces",     "US-70",          68 },
	{ "Albuquerque",    "Santa Fe",       "I-25",           63 },
	{ "Albuquerque",    "Socorro",        "I-25",           76 },
	{ "Albuquerque",    "Clines Corners", "I-40",           61 },
	{ "Albuquerque",    "Grants",         "I-40",           79 },
	{ "Artesia",        "Carlsbad",       "US-285",         36 },
	{ "Artesia",        "Roswell",        "US-285",         41 },
	{ "Carrizozo",      "Clines Corners", "US-285/US-54",  109 },
	{ "Carrizozo",      "Roswell",        "US-380",         90 },
	{ "Carrizozo",      "Socorro",        "US-380",         76 },
	{ "Clines Corners", "Santa Fe",       "US-285",         54 },
	{},
	{},
	{},

	  };

void sampleAStar()
{
	typedef std::string State;

	struct Route
	{
		State prev;
		double pathCost;
	};

	typedef com::foiani::node_set< State, double, Route > Routes;
	typedef Routes::node_type node_type;

	Routes routes;

	const State orig = "(0,0)";
	const State dest = "(10,10)";

	BOOST_CHECK( routes.insert( { "(0,0)", 1000000.0 } ) );

	typedef std::unordered_set< std::string > ClosedSet;
	ClosedSet closed;

	node_type node;
	BOOST_CHECK( routes.get_min_cost_node( node ) );
	while ( node.state() != dest )
	{
		IF_DEBUGGING( nodes.dump( std::clog ) );

		routes.eraseMinCost();
		closed.insert( node.state() );

		const std::string id( node.state() );

		const std::size_t xStart = id.find( "(" ) + 1;
		const std::size_t xEnd   = id.find( ",", xStart );
		const std::size_t yStart = xEnd + 1;
		const std::size_t yEnd   = id.find( ")", yStart );

		const int x = strToInt( id.substr( xStart, xEnd - xStart ) );
		const int y = strToInt( id.substr( yStart, yEnd - yStart ) );

		std::ostringstream oss;
		for ( int dx = -1; dx <= 1; ++dx )
		{
			for ( int dy = -1; dy <= 1; ++dy )
			{
				oss.str( "" );
				oss << "(" << x + dx << "," << y + dy << ")";

				const double stepCost = ( node.path_cost() +
										  ( dx < 0 ? -dx : dx ) +
										  ( dy < 0 ? -dy : dy ) );



				routes.insert_or_update( { oss.str(), node.path_cost() + stepCost, node.state() } );
			}
		}
	}
}

#endif

}

// =====================================================================

int test_main( int argc, char * argv [] )
{
	testBasics();
	// sampleAStar();
	return 0;
}

// Local Variables:
// mode: c++
// tab-width: 4
// indent-tabs-mode: t
// End:
